package com.mj.set.tree;

import java.util.Comparator;

public class BBST<E> extends BST<E> {
    public BBST() {
        this(null);
    }

    /**
     * 调用父类的构造方法 传入comparator 比较器
     *
     * @param comparator
     */
    public BBST(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 左旋
     */
    protected void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;//T1
        grand.right = child;
        parent.left = grand;
        //更新的T、p、g parent 属性
        afterRotate(grand, parent, child);
    }

    /**
     * 右旋
     */
    protected void rotateRight(Node<E> grand) {

        Node<E> parent = grand.left;
        Node<E> child = parent.right;//T2
        grand.left = child;
        parent.right = grand;
        //更新T、p、g的 parent 属性
        afterRotate(grand, parent, child);
    }

    /**
     * 更新p、T2、g的 parent 属性
     * <p>
     * 公共代码:不管是左旋转、右旋转，都要执行的
     *
     * @param grand  失衡节点
     * @param parent 失衡节点的tallerChild
     * @param child  g和p需要交换的子树（本来是p的子树，后面会变成g的子树)
     */
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {

        //parent成为子树的根节点
        parent.parent = grand.parent;
        //还要让grand.parent的左右子树节点指向parent
        //先判断grand是父节点的左子节点还是右子节点
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {
            //如果grand不是左右子节点，那么就是根节点
            root = parent;
        }

        //更新child的parent (子树可能为空)
        if (child != null) {
            child.parent = grand;
        }
        //更新grand的parent
        grand.parent = parent;

//        //更新高度 只有AVL树存在高度
//        updateHeight(grand);
//        updateHeight(parent);
    }

    /**
     * 统一所有旋转操作
     */
    protected void rotate(
            Node<E> r,//子树的根节点
            Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f
    ) {
        //让D成为这棵树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        //处理 b,c
        b.right = c;
        if (c != null) {
            c.parent = b;
        }


        //处理 e,f,g
        f.left = e;
        if (e != null) {
            e.parent = f;
        }


        //d-b-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;


    }
}
